from typing import *
from math import inf
from sortedcontainers import SortedSet
from bisect import bisect_left, bisect_right


class Solution:

    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        ss, ans = SortedSet(), inf
        ss.add(-inf)
        ss.add(inf)
        for i, v in enumerate(nums):
            if i - x >= 0:
                ss.add(nums[i - x])
                ans = min(ans, abs(v - ss[bisect_left(ss, v)]),
                          abs(v - ss[bisect_right(ss, v) - 1]))

        return ans


class Solution:

    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        ss, ans = SortedSet(), inf
        ss.add(-inf)
        ss.add(inf)
        for i, v in enumerate(nums):
            if i - x >= 0:
                ss.add(nums[i - x])
                j = bisect_left(ss, v)
                ans = min(ans, abs(v - ss[j]), abs(v - ss[j - 1]))

        return ans

class Solution:

    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        ss, ans = SortedSet(), inf
        ss.add(-inf)
        ss.add(inf)
        for i in range(x,len(nums)):
            ss.add(nums[i - x])
            j = bisect_left(ss, nums[i])
            ans = min(ans, abs(nums[i] - ss[j]), abs(nums[i] - ss[j - 1]))

        return ans
    
from sortedcontainers import SortedList
class Solution:

    def minAbsoluteDifference(self, nums: List[int], x: int) -> int:
        ss, ans = SortedList(), inf
        ss.add(-inf)
        ss.add(inf)
        for i in range(x,len(nums)):
            ss.add(nums[i - x])
            j = bisect_left(ss, nums[i])
            ans = min(ans, abs(nums[i] - ss[j]), abs(nums[i] - ss[j - 1]))

        return ans
s = Solution()
print(s.minAbsoluteDifference(nums=[1, 2, 3, 4], x=3))



# nums = [5,3,2,10,15]

# for k,v in zip(nums,nums[2:]):
#     print(k,v)
